1. Field of the Invention
This invention relates to the monitoring of jitter in a data stream passing through a network router or switch configured to provide expedited forwarding (EF) of the data stream. More particularly, it relates to the use of the depths of an output queue at enqueue times to ascertain the worst-case jitter characteristics of data streams passing through the queue.
2. Background Information
In data networks, nodes such as routers and switches may be equipped to provide differential services for different classes of traffic. Specifically, they may operate to apply per-hop behaviors (PHB's) for forwarding designated classes of data packets to downstream nodes. One of these PHB's, termed “Expedited Forwarding” (EF) is used, for example, to provide a virtual wired connection between the endpoints of traffic having this designation.
Expedited Forwarding is thus a premium service that commands relatively high revenues from those who have requested it. However it requires the ability of the network nodes between the endpoints to pass essentially interrupted data streams between the endpoints. Inevitably, there is, at least occasionally, some jitter in these transmissions. The jitter can be caused by a number of factors, one of which, “EF on EF” jitter, is the subject of the present invention. This jitter results from the use of a single output line for multiple EF packet streams: a packet burst in one stream can increase the latency in the other streams.
For example, consider a packet stream A serviced by a router, along with other streams, by the EF PHB. If, at enqueue time of packet A(n), the depth of the output queue through which the stream passes is Q(n) and at enqueue time of packet A(n+1), the EF queue depth is Q(n+1), then the per hop EF-on-EF jitter for these two consecutive packets of stream A is [Q(n+1)−Q(n)]/EF service rate. As the EF is serviced with priority to any other PHB, the EF service rate is equal to the link rate of the output line. Hence the jitter between any two consecutive packets of a stream A is equal to [Q(n+1)−Q(n)]/link rate. It is impossible to memorize these Q(.) values for all the streams mixed in an EF output queue (there could be 1000's of them at any time) and hence it is very difficult to measure the per hop EF-on-EF jitter.
The endpoints can accommodate some degree of jitter by buffering the arriving packets so as to provide a continuous output stream to a device, such as telephone processing circuitry, that processes the data in the incoming stream. However, the degree of buffering that can be applied at an end point is limited, largely by latency considerations. Thus the per-hop jitters encountered at the intermediate nodes between the endpoints must be kept below certain limits so as not to exceed the limits of endpoint buffering. This requires that the service provider monitor the jitter at each of the intermediate network nodes so that corrective action can be taken when the jitter imposed on the data stream by the node falls outside certain limits set by the service provider. There may be a number of locations in a router or switch that may manifest jitter and most of these can be is measured and dealt with by the service providers who operate these devices.
However, jitter, which may be defined as the difference in delay between consecutive data packets, is difficult to determine in practice in the Priority Queues which deliver EF packets to the lines that pass the packets to downstream devices. In such a queue jitter is the result of the fact that more than one EF data packet stream passes through the queue and changes in traffic flow in one packet stream can cause corresponding jitters in other packet streams flowing through the same queue.